#include "StdAfx.h"
#include "Graph.h"
#include <sstream>
#include <iostream>
#include <fstream>
#define uint unsigned int

using namespace std;

// =========== Edge Class Implementation =================================================

// Constructors & Destructors

Graph::Edge::Edge(uint a, uint b): 
	_cost(0), _first(a), _second(b) {
}

Graph::Edge::Edge(uint a, uint b, int cost): 
	_cost(cost), _first(a), _second(b) {
}

Graph::Edge::Edge(const Edge& e): 
	_cost(e._cost), _first(e._first), _second(e._second) {
}

Graph::Edge::~Edge(void) {
}

// Getters & Setters

bool Graph::Edge::setCost(int cost) {
	_cost = cost;
	return true;
}

int Graph::Edge::getCost(void) const {
	return _cost;
}

uint Graph::Edge::getFirst(void) const {
	return _first;
}

uint Graph::Edge::getSecond(void) const {
	return _second;
}

// Operator Overloading

bool Graph::Edge::operator==(Edge const& edge) const {
	return (this->getFirst() == edge.getFirst() &&
			this->getSecond() == edge.getSecond());
}

bool Graph::Edge::operator!=(Edge const& edge) const {
	return !(*this == edge);
}

bool Graph::Edge::operator<(Edge const& e2) const {
	Edge const& e1  = *this;
	if(e1.getFirst() > e2.getFirst()) {
		return false;
	} else if(e1.getFirst() < e2.getFirst()) {
		return true;
	} else if(e1.getSecond() < e2.getSecond()) {
		return true;
	}
	return false;
}

bool Graph::Edge::operator>  (Edge const& e2) const {
	Edge const& e1  = *this;
	if(e1.getFirst() < e2.getFirst()) {
		return false;
	} else if(e1.getFirst() > e2.getFirst()) {
		return true;
	} else if(e1.getSecond() > e2.getSecond()) {
		return true;
	}
	return false;
}

Graph::Edge& Graph::Edge::operator= (const Edge& edge) {
	this->_first = edge._first;
	this->_second = edge._second;
	this->_cost	= edge._cost;
	return *this;
}

// To String Function

string Graph::Edge::toString(void) {
	stringstream ss;
	ss<<"e:("<<_first<<','<<_second<<") c: "<<_cost;
	return ss.str();
}


// =========== Graph Class Implementation =================================================

Graph::Graph(void) : _vertNR(0) {
	_edges.resize(_vertNR+1);
	_edgesInverted.resize(_vertNR+1);
	_inDegree.resize(_vertNR+1);
	_outDegree.resize(_vertNR+1);
}

Graph::Graph(uint vertNR) : _vertNR(vertNR) {
	_edges.resize(_vertNR+1);
	_edgesInverted.resize(_vertNR+1);
	_inDegree.resize(_vertNR+1);
	_outDegree.resize(_vertNR+1);
}

Graph::~Graph(void) {
}

void Graph::setVertNumber(int vertNR) {
	_vertNR = vertNR;
	_edges.resize(_vertNR+1);
	_edgesInverted.resize(_vertNR+1);
	_inDegree.resize(_vertNR+1);
	_outDegree.resize(_vertNR+1);
}

int Graph::getVertNumber(void) const {
	return _vertNR;
}

Graph::Edge* Graph::getEdge(uint first, uint second) const {
	set<Edge>::iterator it = _edges[first].find(Edge(first, second));
	if (it != _edges[first].end())
		return (Edge*)&(*it);
	else 
		return NULL;
}

int Graph::getCost(const Edge& edge) const {
	return edge.getCost();
}

int Graph::getCost(uint first, uint second) const {
	set<Edge>::iterator it = _edges[first].find(Edge(first, second));
	if (it != _edges[first].end())
		return it->getCost();
	else 
		return 0;
}

bool Graph::setCost(Edge& edge, int cost) {
	return edge.setCost(cost);
}

bool Graph::setCost(uint first, uint second, int cost) {
	set<Edge>::iterator it = _edges[first].find(Edge(first, second));
	if (it != _edges[first].end())
		return ((Edge*)&it)->setCost(cost);
	else
		return 0;
}

uint Graph::getOutDegree(uint v) const {
	return _outDegree[v];
}

uint Graph::getInDegree(uint v) const {
	return _inDegree[v];
}

pair<int,int> Graph::getEndpoints(Edge& edge) const {
	return pair<int,int>(edge.getFirst(), edge.getSecond());
}

vector<uint> Graph::iterateOut(uint vert) {
	vector<uint> v;
	for(set<Edge>::iterator it = _edges[vert].begin(); it != _edges[vert].end(); ++it) {
		v.push_back(it->getSecond());
	}
	return v;
}

vector<uint> Graph::iterateIn(uint vert) {
	vector<uint> v;
	for(set<Edge>::iterator it = _edgesInverted[vert].begin(); it != _edgesInverted[vert].end(); ++it) {
		v.push_back(it->getSecond());
	}
	return v;
}

bool Graph::addEdge(uint first, uint second) {
	if( (_edges[first].insert(Edge(first, second))).second == true ) {
		_outDegree[first]++;
		_edgesInverted[second].insert(Edge(second, first));
		_inDegree[second]++;
		return true;
	} 
	return false;
}

bool Graph::addEdge(uint first, uint second, int cost) {
	Edge e(first, second, cost);
	Edge ie(second, first, cost);

	if( (_edges[first].insert(e)).second == true ) {
		_outDegree[first]++;
		_edgesInverted[second].insert(ie);
		_inDegree[second]++;
		return true;
	} 
	return false;
}

bool Graph::removeEdge(uint first, uint second) {
	set<Edge>::iterator it = _edges[first].find(Edge(first, second));
	if (it != _edges[first].end())
		if ((_edges[first].erase(*it)) == 1) {
			_outDegree[first]--;
			_inDegree[second]--;
			return true;
		}
	return false;
}

bool Graph::removeEdge(Edge& edge) {
	int first = edge.getFirst();
	int second = edge.getSecond();
	if ((_edges[edge.getFirst()].erase(edge)) == 1) {
		_outDegree[first]--;
		_inDegree[second]--;
		return true;		
	}
	return false;
}

bool Graph::isEmpty(void) {
	return (_vertNR == 0);
}

bool Graph::isEdge(uint first, uint second) {
	set<Edge>::iterator it = _edges[first].find(Edge(first, second));
	if (it != _edges[first].end())
		return true;
	else 
		return false;
}

bool Graph::readGraph(const string fileName) {
	ifstream fd(fileName.c_str(), ifstream::in);
	string line;
	int n, m, v[3];
	if(fd.is_open()){
		fd >> n; fd >> m;
		this->setVertNumber(n);
		for(int i = 0; i < m; i++) {
			fd >> v[0];
			fd >> v[1];
			fd >> v[2];
			this->addEdge(v[0], v[1], v[2]);
		}
		fd.close();
		return true;
	} else 
		return false;
}   

vector<uint> Graph::BFS(uint first, uint last) {
	queue<uint> Q;
	vector<uint> visited;
	visited.resize(this->_vertNR, -1); // -1 means vert was not visited
	uint vert;
	Q.push(first);
	visited[first] = -2; // -2 means it has no parent in the resulting vert list
	while(!Q.empty()) {
		vert = Q.front();
		Q.pop();
		if(vert == last) {
			break;
		}
		vector<uint> outbound = this->iterateOut(vert);
		for(vector<uint>::iterator it = outbound.begin(); it != outbound.end(); it++) {
			if( visited[*it] == -1 ) {
				visited[*it] = vert;
				Q.push(*it);
			}
		}
	}
	
	vector<uint> path;
	int searched = last;
	do {
		path.insert(path.begin(), searched);
		searched = visited[searched];
	} while(searched != -2 && searched != -1);

	return path;
}